সেগমেন্ট ট্রি এবং ফেনউইক ট্রি

সেগমেন্ট ট্রি এবং ফেনউইক ট্রি (যা বাইট ট্রি বা ফেনউইক টেবিল নামেও পরিচিত) হল দুটি বিশেষ ডেটা স্ট্রাকচার যা অ্যারে বা লিস্টের বিভিন্ন ক্যালকুলেশন (যেমন সমষ্টি, গড়, মিনিমাম, ম্যাক্সিমাম) দ্রুততর করার জন্য ব্যবহৃত হয়।

১. সেগমেন্ট ট্রি (Segment Tree)

বর্ণনা

সেগমেন্ট ট্রি একটি বাইনারি ট্রি যা একটি অ্যারের বিভিন্ন সেগমেন্ট বা উপসেটের উপর অপারেশন করার জন্য ব্যবহৃত হয়। এটি সাধারণত একটি ডেটা স্ট্রাকচার যা একটি নির্দিষ্ট রেঞ্জের জন্য মান এবং তাদের সংশ্লিষ্ট বৈশিষ্ট্য (যেমন সমষ্টি, মিনিমাম) দ্রুত পেতে সহায়ক।

বৈশিষ্ট্য

• বিল্ডিং টাইম: O(n)
• আপডেট টাইম: O(log n)
• কোয়েরি টাইম: O(log n)

উদাহরণ কোড (Python):

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (2 * self.n)
        self.build(data)

    def build(self, data):
        # লিফ নোডগুলিকে অ্যারের মান দিয়ে পূরণ করা
        for i in range(self.n):
            self.tree[self.n + i] = data[i]
        # অভ্যন্তরীণ নোডগুলি তৈরি করা
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]

    def update(self, index, value):
        # মান আপডেট করা
        index += self.n
        self.tree[index] = value
        while index > 1:
            index //= 2
            self.tree[index] = self.tree[index * 2] + self.tree[index * 2 + 1]

    def query(self, left, right):
        # রেঞ্জ ক্যালকুলেশন (sum)
        left += self.n
        right += self.n
        result = 0

        while left < right:
            if left & 1:  # যদি left odd হয়
                result += self.tree[left]
                left += 1
            if right & 1:  # যদি right odd হয়
                right -= 1
                result += self.tree[right]
            left //= 2
            right //= 2

        return result

# উদাহরণ
data = [1, 3, 5, 7, 9, 11]
seg_tree = SegmentTree(data)

print("Sum of values in range (1, 5):", seg_tree.query(1, 5))  # Output: 24
seg_tree.update(1, 10)  # data[1] = 10
print("Sum of values in range (1, 5) after update:", seg_tree.query(1, 5))  # Output: 30

২. ফেনউইক ট্রি (Fenwick Tree)

বর্ণনা

ফেনউইক ট্রি, যা বাইট ট্রি (Binary Indexed Tree) নামেও পরিচিত, একটি ডেটা স্ট্রাকচার যা কার্যকরভাবে রেঞ্জ ক্যালকুলেশন এবং আপডেটের জন্য ব্যবহার করা হয়। এটি সাধারণত সমষ্টি এবং আপডেট অপারেশন করার জন্য ব্যবহৃত হয়।

বৈশিষ্ট্য

• বিল্ডিং টাইম: O(n)
• আপডেট টাইম: O(log n)
• কোয়েরি টাইম: O(log n)

উদাহরণ কোড (Python):

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, index, delta):
        while index <= self.size:
            self.tree[index] += delta
            index += index & -index

    def query(self, index):
        sum_value = 0
        while index > 0:
            sum_value += self.tree[index]
            index -= index & -index
        return sum_value

# উদাহরণ
data = [1, 3, 5, 7, 9, 11]
fenwick_tree = FenwickTree(len(data))

# আপডেট
for i, value in enumerate(data):
    fenwick_tree.update(i + 1, value)  # 1-indexed

print("Sum of first 5 elements:", fenwick_tree.query(5))  # Output: 25
fenwick_tree.update(3, 6)  # data[3] += 6
print("Sum of first 5 elements after update:", fenwick_tree.query(5))  # Output: 31

উপসংহার

সেগমেন্ট ট্রি এবং ফেনউইক ট্রি উভয়ই কার্যকরী ডেটা স্ট্রাকচার যা অ্যারে এবং লিস্টের উপর দ্রুত আপডেট এবং কোয়েরি অপারেশন করার জন্য ব্যবহৃত হয়। সেগমেন্ট ট্রি সাধারণত জটিল এবং বিভিন্ন ধরনের ক্যালকুলেশনের জন্য ব্যবহৃত হয়, যখন ফেনউইক ট্রি সাধারণত রেঞ্জ ক্যালকুলেশন এবং আপডেটের জন্য আরো কার্যকরী। উভয় ডেটা স্ট্রাকচার বিভিন্ন অ্যালগরিদমিক সমস্যা সমাধানে অত্যন্ত গুরুত্বপূর্ণ।